#include "BTreeNode.h"
#include "stdio.h"
#include <cstring>
#include <stdlib.h>
using namespace std;

/*
Constructor
*/
BTLeafNode::BTLeafNode()
{
	//Set the first PAGE_SIZE bytes of memory pointed by buffer to 0
	memset(buffer, 0, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	//Set the first PAGE_SIZE bytes of memory pointed by buffer to 0
	memset(buffer, 0, PageFile::PAGE_SIZE);
	
	//Save the PageFile and PageID of this node
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int numKeys = 0;
	//Copy the first four bytes since thats where the number of records in a page is saved.
	memcpy(&numKeys, &buffer, sizeof(int));
	return numKeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	//Variables
	int entry_size = sizeof(RecordId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(PageId) + sizeof(int);
	int openKey;
	int counter = 0;

	char* buffer2 = (char*)malloc(PageFile::PAGE_SIZE);
	memset(buffer2, 0, PageFile::PAGE_SIZE);

	//Check to see if there are empty nodes
	if(getKeyCount() >= 84)
		return RC_NODE_FULL;

	//Get the last empty node
	while(iterator)
	{
		memcpy(&openKey, iterator, sizeof(int));
		if(openKey == 0)
			break;

		if(key > openKey) {
			iterator = iterator + entry_size;
			counter++;
		}
		else
			break;
	}

	//Error checking for nodes
	if(&(buffer[PageFile::PAGE_SIZE]) - iterator < 20)
		return RC_NODE_FULL;

	//Shift entries in the buffer
	if(openKey != 0 && full_size > 0) {
		memcpy(buffer2, iterator, full_size - entry_size*counter);
		memset(iterator, 0, full_size - entry_size*counter);
	}

	//Insert the key and RecordId
	memcpy(iterator, &key, sizeof(int));
	iterator = iterator + sizeof(int);
	memcpy(iterator, &rid, sizeof(RecordId));
	iterator = iterator + sizeof(RecordId);
	if(openKey != 0 && full_size > 0)
		memcpy(iterator, buffer2, full_size - entry_size*counter);
	free(buffer2);

	//Update the key count
	int newKC = getKeyCount();
	newKC++;
	iterator = buffer;
	memcpy(iterator, &newKC, sizeof(int));
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	//Variables
	int entry_size = sizeof(RecordId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(PageId) + sizeof(int);
	int counter = 0;

	while(counter < (getKeyCount() / 2))
	{
		iterator = iterator + entry_size;
		counter++;
	}

	char* buffer2 = (char*)malloc(PageFile::PAGE_SIZE);
	char* ptr = buffer2;
	memset(buffer2, 0, PageFile::PAGE_SIZE);
	memcpy(buffer2, iterator, full_size - entry_size*(getKeyCount() / 2));

	memset(iterator, 0, full_size - entry_size*(getKeyCount() / 2));
	int kc = (getKeyCount() / 2);
	memcpy(buffer, &kc, sizeof(int));

	while(buffer2)
	{
		int i;
		RecordId rid2;

		memcpy(&i, buffer2, sizeof(int));
		if(i == 0)
			break;

		buffer2 = buffer2 + sizeof(int);
		memcpy(&rid2, buffer2, sizeof(RecordId));
		buffer2 = buffer2 + sizeof(RecordId);

		/*
		if(rid2.pid == 0 && rid2.sid == 0 && i != 272) {
			//return RC_FILE_WRITE_FAILED
		}
		*/

		if(sibling.insert(i, rid2) != 0) {
			free(ptr);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(ptr);

	RecordId rid3;
	if(sibling.readEntry(0, siblingKey, rid3) != 0)
		return RC_FILE_WRITE_FAILED;

	if(key < siblingKey) {
		if(insert(key, rid) != 0)
			return RC_FILE_WRITE_FAILED;
	}
	else {
		if(sibling.insert(key, rid) != 0)
			return RC_FILE_WRITE_FAILED;
	}
	
	if(sibling.readEntry(0, siblingKey, rid3) != 0)
		return RC_FILE_WRITE_FAILED;
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	//Variables
	int entry_size = sizeof(RecordId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(int);
	int counter = 0;
	int openKey;

	while(iterator)
	{
		memcpy(&openKey, iterator, sizeof(int));

		if(openKey == 0 || openKey >= searchKey) {
			eid = counter;
			break;
		}

		iterator = iterator + entry_size;
		counter++;
	}
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	//Variables
	int entry_size = sizeof(RecordId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(PageId) + sizeof(int);
	int counter = 0;
	
	while(iterator && counter < eid)
	{
		iterator = iterator + entry_size;
		counter++;
	}

	memcpy(&key, iterator, sizeof(int));
	iterator = iterator + sizeof(int);
	memcpy(&rid, iterator, sizeof(RecordId));
	return 0;

}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	char* iterator = buffer;
	iterator = iterator + sizeof(int);
	PageId pid;

	memcpy(&pid, iterator, sizeof(PageId));
	return pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* iterator = buffer;
	iterator = iterator + sizeof(int);

	memcpy(iterator, &pid, sizeof(PageId));
	return 0;
}

/*
Constructor
*/
BTNonLeafNode::BTNonLeafNode()
{
	//Set the first PAGE_SIZE bytes of memory pointed by buffer to 0
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int numKeys = 0;
	//Copy the first four bytes since thats where the number of records in a page is saved.
	memcpy(&numKeys, &buffer, sizeof(int));
	return numKeys;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	//Variables
	int entry_size = sizeof(PageId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(PageId) + sizeof(int);
	int counter = 0;
	int openKey;

	char* buffer2 = (char*)malloc(PageFile::PAGE_SIZE);
	memset(buffer2, 0, PageFile::PAGE_SIZE);

	//Check to see if there are empty nodes
	if(full_size >= PageFile::PAGE_SIZE - entry_size)
		return RC_NODE_FULL;

	//Get the last empty node
	while(iterator)
	{
		memcpy(&openKey, iterator, sizeof(int));
		if(openKey == 0)
			break;

		if(key > openKey) {
			iterator = iterator + entry_size;
			counter++;
		}
		else
			break;
	}	

	if(openKey == key) {
		iterator = iterator + sizeof(int);
		memcpy(iterator, &pid, sizeof(PageId));
		return 0;
	}

	//Error checking for nodes
	if(iterator == &(buffer[PageFile::PAGE_SIZE]))
		return RC_NODE_FULL;

	//Shift entries in the buffer
	if(openKey != 0 && full_size > 0) {
		memcpy(buffer2, iterator, full_size - entry_size*counter);
		memset(iterator, 0, full_size - entry_size*counter);
	}

	//Insert the key and PageId
	memcpy(iterator, &key, sizeof(int));
	iterator = iterator + sizeof(int);
	memcpy(iterator, &pid, sizeof(PageId));
	iterator = iterator + sizeof(PageId);
	if(openKey != 0 && full_size > 0)
		memcpy(iterator, buffer2, full_size - entry_size*counter);
	free(buffer2);

	//Update the key count
	int newKC = getKeyCount();
	newKC++;
	iterator = buffer;
	memcpy(iterator, &newKC, sizeof(int));
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ //Variables
	int entry_size = sizeof(PageId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + sizeof(int);
	int counter = 0;

	while(counter < (getKeyCount() / 2))
	{
		iterator = iterator + entry_size;
		counter++;
	}

	char* buffer2 = (char*)malloc(PageFile::PAGE_SIZE);
	char* ptr = buffer2;
	memset(buffer2, 0, PageFile::PAGE_SIZE);
	memcpy(buffer2, iterator, full_size - entry_size*(getKeyCount() / 2));

	memset(iterator, 0, full_size - entry_size*(getKeyCount() / 2));
	int kc = (getKeyCount() / 2);
	memcpy(buffer, &kc, sizeof(int));

	while(buffer2)
	{
		int i;
		PageId pid2;

		memcpy(&i, buffer2, sizeof(int));
		if(i == 0)
			break;

		buffer2 = buffer2 + sizeof(int);
		memcpy(&pid2, buffer2, sizeof(PageId));
		buffer2 = buffer2 + sizeof(PageId);

		/*
		if(rid2.pid == 0 && rid2.sid == 0 && i != 272) {
			//return RC_FILE_WRITE_FAILED
		}
		*/

		if(sibling.insert(i, pid2) != 0) {
			free(ptr);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(ptr);

	if(sibling.readEntry(0, midKey) != 0)
		return RC_FILE_WRITE_FAILED;

	if(key < midKey) {
		if(insert(key, pid) != 0)
			return RC_FILE_WRITE_FAILED;
	}
	else {
		if(sibling.insert(key, pid) != 0)
			return RC_FILE_WRITE_FAILED;
	}
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	//Variables
	int entry_size = sizeof(RecordId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	
	char* iterator = buffer;
	iterator = iterator + 2*sizeof(int);
	int openKey;

	while(iterator)
	{
		memcpy(&openKey, iterator, sizeof(int));

		if(openKey != 0 || openKey < searchKey)
			iterator = iterator + sizeof(int);
		else {
			iterator = iterator - sizeof(PageId);
			memcpy(&pid, iterator, sizeof(PageId));
			break;
		}
		iterator = iterator + entry_size;
	}
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	char* iterator = buffer;
	iterator = iterator + sizeof(int);

	memcpy(iterator, &pid1, sizeof(PageId));
	iterator += sizeof(PageId);

	memcpy(iterator, &key, sizeof(int));
	iterator += sizeof(int);

	memcpy(iterator, &pid2, sizeof(PageId));

	int i = 0;
	memcpy(buffer, &i, sizeof(int));
	return 0;
}

RC BTNonLeafNode::readEntry(int eid, int& key) {
	//Variables
	int entry_size = sizeof(PageId) + sizeof(int);
	int full_size = getKeyCount() * entry_size;
	char* iterator = buffer;
	iterator = iterator + sizeof(int);
	int counter = 0;

	while(iterator) {
		iterator = iterator + sizeof(PageId);
		
		if(counter == eid) {
			memcpy(&key, iterator, sizeof(int));
			break;
		}
		
		iterator = iterator + entry_size;
	}

	return 0;
}